package com.xiaoyu.binaryTree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: DS_and_A
 * @description: 对称二叉树  --> 给定一个二叉树，检查它是否是镜像对称的。
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 *
 *     1
 *    / \
 *   2   2
 *  / \ / \
 * 3  4 4  3
 *
 *
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 *
 *     1
 *    / \
 *   2   2
 *    \   \
 *    3    3
 *
 * @author: YuWenYi
 * @create: 2021-05-17 19:21
 **/
/* 错误代码:
   public static boolean isSymmetricTwoSubTree(TreeNode left,TreeNode right){
        if (left == null && right == null){
        return true;
        }
        boolean b1 = true;
        boolean b2 = true;

        if ((left.left!=null && right.right==null) || (left.left==null && right.right!=null)){
        b1 = false;
        }else {
        if (left.left != null){
        b1 = left.left.val == right.right.val;
        }
        }
        if ((left.right!=null && right.left==null) || (left.right==null && right.left!=null)){
        b2 = false;
        }else {
        if (left.right!=null){
        b2 = left.right == right.left;
        }
        }
        if (left.left!=null && right.right!=null){
        b1 = isSymmetricTwoSubTree(left.left, right.right);
        }

        if (left.right!=null && right.left!=null){
        b2 = isSymmetricTwoSubTree(left.right, right.left);
        }
        return b1 & b2;
        }*/

public class IsSymmetric_101 {

    /*
    * 我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，
    * p 指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q 左移，p 左移时，q 右移。
    * 每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。
    * */
    public static boolean isSymmetric1(TreeNode root) {
        return checkSym(root, root);
    }

    public static boolean checkSym(TreeNode p,TreeNode q){
        if (p == null && q == null){
            return true;
        }
        if (p == null || q == null){
            return false;
        }
        return p.val == q.val && checkSym(p.left, q.right) && checkSym(p.right, q.left);
    }


    //方法二:使用队列加迭代法
    public static boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }

    private static boolean check(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);
        while (!queue.isEmpty()){
            //从队列中取出两个节点，再比较这两个节点
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            //如果两个节点都为空就继续循环，两者有一个为空就返回false
            if(left==null && right==null) {
                continue;
            }
            if ((left==null || right == null) || left.val != right.val){
                return false;
            }

            //将左节点的左孩子， 右节点的右孩子放入队列
            queue.offer(left.left);
            queue.offer(right.right);

            //将左节点的右孩子，右节点的左孩子放入队列
            queue.offer(left.right);
            queue.offer(right.left);
        }
        //能走到这里说明是ture
        return true;
    }


    public static void main(String[] args) {
        //TreeNode node2 = new TreeNode(3);
        TreeNode node1 = new TreeNode(3);
        TreeNode left = new TreeNode(3);
        TreeNode root = new TreeNode(1,left,node1);

        System.out.println(isSymmetric(root));
    }

}
